2018-10-27

Cryptography

密码学知识总结

前言

　　很喜欢这种开放性题目的作业，每个人可以根据自己的兴趣来选择相应的题目。也是一个锻炼自主学习能力的机会。
　　学习密码学用图片可以很难直观地展现算法的流程，推荐一本书《图解密码技术》，书中有大量的图片，可以用来入门。

1 现代密码学

1.1 对称密码体制

1.1.1 简介

　　之所以叫对称密码，是因为加密秘钥与解密秘钥是同一个。这样通讯双方只需要掌握一个秘钥就可以，并且在加密解密的硬件和软件实现上更加容易和高效。

1.1.2 优缺点

1.1.2.1 优点

算法公开
计算量小
加密速度快
加密效率高

1.1.2.2 缺点

双方使用同样钥匙，安全性得不到保证
密钥管理困难，使用成本较高

1.1.3 DES

1.1.3.1 简介

　　DES全称为Data Encryption Standard，即数据加密标准，是一种使用密钥加密的块算法，1977年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），并授权在非密级政府通信中使用，随后该算法在国际上广泛流传开来。传统的DES只有56位的密钥。

1.1.3.2 步骤

　　DES是一种16轮循环的加密算法，并且每一次读入64比特明文。下面是一轮循环的基本步骤：

将输入的数据等分为左右两部分。
将右侧数据直接发送到输出的右侧。
将右侧数据发送到轮函数。
轮函数根据右侧数据和子密钥，计算出一串比特序列。
将上一步得到的比特序列与左侧数据进行XOR运算，并将结果作为加密后的左侧。

1.1.3.3 XOR

　　由于加密解密是同样的密钥，并且为了方便和效率，DES的加密和解密可以用同样的结构来实现，于是正好可以利用异或(同0异1)运算的特性。例如：

十进制数字 6　　0110
异或 5　　　　　0101
结果 3　　　　　0011
再异或 5　　　　0101
结果 6　　　　　0110

　　可以看到异或两次之后，又恢复了原来的数字，其中第一次异或5可以看作加密的过程，第二次异或5就相当于解密的过程。

1.1.4 3DES

　　由于随着计算能力的提高，DES已经可以在现实地时间内被暴力破解，因此需要一种来替代DES的分组密码，于是三重DES被开发出来。简单地说，三重DES就是将DES重复三次，不过并不是进行三次加密，而是加密→解密→加密的过程。当三次操作的密钥相同时，3DES就变成了普通的DES，这一设计实现了对DES的兼容。当三次的密钥都不相同时才是真正的3DES。

1.1.5 AES

1.1.5.1 简介

　　由于3DES的处理速度不高，而且在安全性方面出现一些问题，出现了一种新的对称密码标准AES。AES是采用公开竞选的方式进行的，通过竞争来实现标准化，并且密码算法可以得到所有人的评审。最终AES选定了名为Rijndael的对称密码算法。
　　Rijndael的分组长度为128比特，秘钥长度有128、192、256比特三种。

1.1.5.2 步骤(以128比特为例)

将128比特分为4组，每组四个字节。
将每一组的字节按照一定规律打乱。
与轮密钥进行XOR处理输出。

1.2 公钥密码体制

1.2.1 简介

　　在对称密码中，由于加密解密的密钥是相同的，所以需要向接受者配送密钥，这一问题称为密钥配送问题。于是产生了公钥密码。
　　在公钥密码中有公钥和私钥，发送者用公钥加密，接受者用私钥解密。其中公钥可以公开，私钥是保密的。与对称密码区分开来，公钥密码也叫非对称密码。

1.2.2 优缺点

1.2.2.1 优点

方便解决密钥分发问题
可以应用于签名，进行身份验证
基于数学难题，比较安全

1.2.2.2 缺点

速度较慢
需要安全保存私钥，引入新的问题
有公钥认证问题

1.2.3 数学原理

1.2.3.1 对数&离散对数

7^□=49 我们可以很快求出□中的数字。
7^□mod 13=8，此时我们想要求□就需要进行多次尝试
7⁰mod 13=1
7¹mod 13=7
··· ···
7⁹mod 13=8
当数字很大时，求离散对数是很困难的。

1.2.4 RSA

1.2.4.1 简介

　　RSA是一种公钥密码算法，名字是由三位开发者的姓氏首字母组成。这种算法还可以用于数字签名。

1.2.4.2 加解密

密文=明文^E mod N　　加密
明文=密文^D mod N　　解密
其中E与N的组合就是公钥
D与N的组合是私钥
当然D与E是有着紧密联系的

1.2.4.3 密钥对生成

求N：准备两个很大的质数p,q，N=p*q
求L：L=lcm（p-1,q-1)
求E：使用随机数生成器得到E，使其满足(1\<E\<L) && (gcd(E,L)=1)
求D：求出D，使其满足(1\<D\<L) && (E*D mod L =1)
(E,N)和(D,N)分别为公私钥。

1.2.4.4 对RSA的攻击

暴力破解，目前还没有可行的算法。
中间人攻击

1.2.5 其他公钥密码

1.2.5.1 ELGamal

　　是由Taher ELGamal设计的公钥算法。RSA是利用了质因数分解的困难度，而ELGamal方式是利用mod N下求离散对数的困难度。
　　这种方式有一个缺点，就是经过加密后的密文会变成明文的两倍。

1.2.5.2 Rabin

　　是由Rabin设计的算法，利用了mod N下求平方根的困难度。

1.2.5.3 椭圆曲线密码

　　是最近比较受关注的一种公钥密码算法，他的密钥长度比RSA短。它是通过将椭圆曲线上的特定点进行特殊的乘法运算来实现的，李永乐乘法运算的逆运算非常困难这个特性。

1.3 量子密码体制

1.1.1 简介

　　有望成为“完美的密码技术”，利用光子的量子特性来实现通信，并且利用了以下两个事实：
　　（1）无法准确测出光子的偏振方向。
　　（2）测量行为本身会导致光子的状态发生改变。

1.1.2 特点

有望使一次性密码本成为可行。
以前的密码将会被全部破译。
理论完美，但其中有不完美的人类。

1.4 其他技术

1.4.1 单向散列函数

1.4.1.1 概念

消息→单向散列函数→散列值
根据任意长度消息计算出固定长度的散列值
能够快速计算出散列值
弱抗碰撞性：找到与该条消息散列值相同的另一条消息是很困难的。
强抗碰撞性：找到两条散列值相同的消息(山大王小云破解了MD5的这一特性)
单向性
解决消息的完整性(一致性)问题

1.4.1.2 应用

检测消息是否被篡改
用于基于口令的加密
消息认证码
数字签名
伪随机数生成器

1.4.1.3 具体实例

MD4、MD5
SHA-1、SHA-256、SHA-384、SHA-512

1.4.1.4 攻击

暴力破解
破解强坑碰撞性

1.4.2 消息认证码

1.4.2.1 概念

这是一种用来确认消息在传送之后是否完整的技术。
将消息通过密钥生成消息认证码之后跟加密后的消息一块发送，接收者解密消息之后生成消息认证码判断是否相同。
将密钥与单向散列函数结合的一种技术。
无法解决第三方证明的问题
不能防止否认

1.4.2.2 攻击

重放攻击：M截获A给B发送的消息，然后给B发送100次。(当消息是：给xxxxx汇款xx元。)
防御重放攻击：可以给每条消息添加序号或时间戳。

1.4.3 数字签名

1.4.3.1 概念

就像现实生活中的签字一样，用来判断消息是谁发出的，并且消息发出者本人不能否认。
由私钥对消息进行加密，用公钥进行解密。
可以对消息直接签名/对散列值签名
用来判断软件是否被篡改

1.4.3.2 攻击

中间人攻击

1.4.4 证书

1.4.4.1 概念

认证机构T用自己的私钥来对B的公钥进行签名之后就得到T颁发给B的证书
可以通过判断证书是否正确来判断自己收到的密钥是否合法

1.4.4.2 攻击

攻击者将被签名的公钥替换成自己的。
窃取认证机构私钥进行攻击
利用CRL发布的时间差进行攻击

2 密码算法设计

2.1 思想

混淆（confusion）和扩散(diffusion)

2.2 柯克霍夫原则(Kerckhoffs’s principle)

即使非数学上不可破解，系统也应在实质（实用）程度上无法破解。
系统内不应含任何机密物，即使落入敌人手中也不会造成困扰。
密匙必须易于沟通和记忆，而不须写下；且双方可以容易的改变密匙。
系统应可以用于电讯。
系统应可以携带，不应需要两个人或以上才能使用（应只要一个人就能使用）。
系统应容易使用，不致让用户的脑力过分操劳，也无需记得长串的规则。

3 密码安全性分析

3.1 攻击方式

唯密文攻击：只知道密文
已知明文攻击：知道密文和对应明文
选择明文攻击：知道密文和明文，还可以得到自己所选择的明文的密文
自适应选择明文攻击
选择密文攻击
选择密钥攻击
软磨硬泡攻击：比较有效的攻击，一般通过威胁、勒索、贿赂等方式获取密钥。

3.2 古典密码

频率分析

3.3 现代密码

差分密码分析
线性密码分析
强力攻击

3 参考文献

迎与我分享你的看法。
转载请注明出处：http://taowusheng.cn/